翻訳と辞書 Words near each other ・ Shorty Baker ・ Shorty Barr ・ Shorty Cantlon ・ Shorty Castro ・ Shorty da Prince ・ Shorty Dee ・ Shorty Fuller ・ Shorty Gallagher ・ Shorty Green ・ Shorty Hamilton ・ Shorter University ・ Shorter Views ・ Shorter, Alabama ・ Shorter, Faster, Louder ・ Shorterville, Alabama ・ Shortest common supersequence problem ・ Shortest job next ・ Shortest Path Faster Algorithm ・ Shortest path problem ・ Shortest remaining time ・ Shortest river ・ Shortest seek first ・ Shortest tennis match records ・ Shortest total path length spanning tree ・ Shortest-path tree ・ Shortfin barb ・ Shortfin false moray ・ Shortfin lizardfish ・ Shortfin mako shark ・ Shortfin sandskate Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Shortest common supersequence problem ： ウィキペディア英語版 Shortest common supersequence problem In computer science, the shortest common supersequence problem is a problem closely related to the longest common subsequence problem. Given two sequences X = < x1,...,xm > and Y = < y1,...,yn >, a sequence U = < u1,...,uk > is a common supersequence of X and Y if U is a supersequence of both X and Y. In other words, a shortest common supersequence of strings x and y is a shortest string z such that both x and y are subsequences of z. A shortest common supersequence (scs) is a common supersequence of minimal length. In the shortest common supersequence problem, the two sequences X and Y are given and the task is to find a shortest possible common supersequence of these sequences. In general, an scs is not unique. For two input sequences, an scs can be formed from a longest common subsequence (lcs) easily. For example, if X$()\; =\; abcbdab$ and Y$()\; =\; bdcaba$, the lcs is Z$()\; =\; bcba$. By inserting the non-lcs symbols while preserving the symbol order, we get the scs: U$()\; =\; abdcabdab$. It is quite clear that $r\; +\; t\; =\; m\; +\; n$ for two input sequences. However, for three or more input sequences this does not hold. Note also, that the lcs and the scs problems are not dual problems. For the more general problem of finding a string, S which is a superstring of a set of strings S1,S2,...,Sl, the problem is NP-Complete . Also, good approximations can be found for the average case but not for the worst case.〔 〕 == References == * * 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Shortest common supersequence problem」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.